package class4;

/**
 * 二进制求和
 * 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
 * 示例 1：
 * <p>
 * 输入:a = "11", b = "1"
 * 输出："100"
 * 示例 2：
 * <p>
 * 输入：a = "1010", b = "1011"
 * 输出："10101"
 */
public class Code03_BinaryAdd {
    public static void main(String[] args) {
        String a = "11";
        String b = "1";
        String s = addBinary(a, b);
        System.out.println(s);
    }

    /**
     *假设输入是：
     *
     * java
     * String a = "1010";  // 二进制 10
     * String b = "1011";  // 二进制 11
     * 步骤逐步执行：
     * 初始化：l = 3, s = 3, carry = 0, sum = 0, sb = ""。
     *
     * 第一轮：
     * sum = 0 + 0 + 1 = 1（a[3] = 0, b[3] = 1，carry = 0）
     * sb = "1"
     * carry = 0
     *
     * 第二轮：
     * sum = 0 + 1 + 1 = 2（a[2] = 1, b[2] = 1，carry = 0）
     * sb = "10"
     * carry = 1（进位 1）
     *
     * 第三轮：
     * sum = 1 + 0 + 0 = 1（a[1] = 0, b[1] = 0，carry = 1）
     * sb = "101"
     * carry = 0
     *
     * 第四轮：
     * sum = 0 + 1 + 0 = 1（a[0] = 1, b[0] = 1，carry = 0）
     * sb = "1011"
     * carry = 0
     *
     * 最终结果：反转 sb 得到 "11001"。
     * 最终返回结果为 "11001"，即 10 + 11 = 11001（二进制加法的结果）。
     */
    public static String addBinary(String a, String b) {
        int l = a.length() - 1;
        int s = b.length() - 1;

        int sum; //用来存储当前位的和。每一轮加法会计算当前位的结果并存储在这个变量中。
        int carry = 0; //用来保存当前位的进位，初始值为 0。
        StringBuilder sb = new StringBuilder(); //用于构建结果字符串

        /**
         * s >= 0：表示字符串 b 还有位数未处理完（即 b 还有剩余的二进制位）。
         * l >= 0：表示字符串 a 还有位数未处理完（即 a 还有剩余的二进制位）。
         * carry != 0：表示当前的加法结果有进位需要处理。
         */
        while (s >= 0 || l >= 0 || carry != 0) {
            sum = carry; //每次开始处理新的一位时，我们先将 carry 的值加到 sum 中。carry 代表前一位加法产生的进位。
            if (l >= 0) {
                // a 中当前位（从右向左）的字符，使用 a.charAt(l) - '0' 将字符转换为整数（'0' 转换为 0，'1' 转换为 1），并将其加到 sum 中。然后，l-- 将 l 向左移动到下一个数字。
                sum += a.charAt(l) - '0';
                l--;
            }
            if (s >= 0) {
                sum += b.charAt(s) - '0';
                s--;
            }
            // sum & 1 通过按位与操作获取当前位的二进制结果。
            sb.append(sum % 1);
            // 如果 sum 大于或等于 2（例如 2 或 3），就需要进位 1。通过除以 2 计算进位。
            carry = sum / 2;
        }
        return sb.reverse().toString();
    }
}
